package com.test.ssss;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Sout {
    private static int count = 0;
    private static final Object lock = new Object();


    public static void main(String[] args) {
//        a a = new a();
//        a b = new a();
//        a c = new a();
//        Thread even = new Thread(a);
//        Thread odd = new Thread(b);
//        Thread odd1 = new Thread(c);
//        even.start();
//        odd.start();
//        odd1.start();
//
//        maxProduct(new String[]{"abcw", "baz", "foo", "bar", "xtfn", "abcdef"});
//        System.out.println(4194311 & 8388608);



    }

    static class a implements Runnable {

        @Override
        public void run() {
            while (count < 100) {
                synchronized (lock) {
                    System.out.println(Thread.currentThread().getName() + ": " + count++);
                    lock.notifyAll();
                    if (count < 100) {
                        try {
                            lock.wait();
                        } catch (InterruptedException e) {
                            throw new RuntimeException(e);
                        }
                    }
                }
            }
        }
    }

    public int[] countBits(int n) {
        int[] ints = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            if (i % 2 == 0) {
                ints[i] = ints[i / 2];
            } else ints[i] = ints[i - 1] + 1;

        }
        return ints;
    }

    public int singleNumber(int[] nums) {
        if (nums.length == 1) return nums[0];
        Arrays.sort(nums);
        if (nums[0] != nums[1]) return nums[0];
        if (nums[nums.length - 1] != nums[nums.length - 2]) return nums[nums.length - 1];
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] != nums[i + 1] && nums[i + 1] != nums[i + 2]) return nums[i + 1];
        }
        return nums[0];
    }

    public static int maxProduct(String[] words) {
        int wordsLength = words.length;
        int[] length = new int[wordsLength];
        int[] ints = new int[wordsLength];
        int max = 0;
        for (int i = 0; i < wordsLength; i++) {
            length[i] = words[i].length();
            for (char a :
                    words[i].toCharArray()) {
                ints[i] = ints[i] | (1 << (a - 'a'));
            }
            for (int j = 0; j < i; j++) {
                if ((ints[i] & ints[j]) == 0) max = Math.max(max, length[i] * length[j]);
            }

        }
        return max;

    }

    public static int[] twoSum1(int[] numbers, int target) {

        int[] ints = new int[2];
        for (int i = 0; i < numbers.length; i++) {
            int a = target - numbers[i];
            int high = numbers.length - 1;
            int low = i + 1;

            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (a == numbers[mid]) {
                    ints[0] = i;
                    ints[1] = mid;
                    return ints;
                } else if (a > numbers[mid]) {
                    low = mid + 1;
                } else high = mid - 1;

            }


        }
        return new int[
                ]{-1, -1};
    }

    public int[] twoSum(int[] numbers, int target) {
        int start = 0;
        int end = numbers.length - 1;
        while (start < end) {
            int nums = numbers[start] + numbers[end];
            if (nums == target) {
                return new int[]{start, end};

            } else if (nums < target) {
                start++;

            } else end--;

        }
        return new int[]{-1, -1};

    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3 = new int[m + n];
        while (m - 1 >= 0 || n - 1 >= 0) {
            if (m - 1 < 0) {
                for (int i = 0; i < n; i++) {
                    nums3[i] = nums2[i];
                }
                break;
            }
            if (n - 1 < 0) {
                for (int i = 0; i < m; i++) {
                    nums3[i] = nums1[i];
                }
                break;
            }
            if (nums1[m - 1] >= nums2[n - 1]) {
                nums3[m + n - 1] = nums1[m - 1];
                m--;
            } else {
                nums3[m + n - 1] = nums2[n - 1];
                n--;
            }

        }
        for (int i = 0; i < nums3.length; i++) {
            nums1[i] = nums3[i];
        }
    }


    public int trap(int[] height) {
        int length = height.length;
        if (length == 0) return 0;
        int[] left = new int[length];
        left[0] = height[0];
        for (int i = 1; i < length; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }
        int[] right = new int[length];
        right[length - 1] = height[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }
        int count = 0;
        for (int i = 0; i < length; i++) {
            count = count + Math.min(left[i], right[i]) - height[i];
        }
        return count;

    }

    public static int[] asteroidCollision1(int[] asteroids) {
        int[] ints = Arrays.stream(asteroids).filter(x -> x != 0).toArray();
        if (ints.length == 0) return ints;
        asteroids = ints;
        int count = 0;
        for (int i = asteroids.length - 1; i > 0; i--) {
            int b = asteroids[i - 1];
            int a = asteroids[i];
            if (a < 0 && b > 0) {
                if (Math.abs(a) > Math.abs(b)) {
                    asteroids[i - 1] = 0;
                } else if (Math.abs(a) < Math.abs(b)) {
                    asteroids[i] = 0;
                } else {
                    asteroids[i] = 0;
                    asteroids[i - 1] = 0;
                }
            }
            if (asteroids[i] == 0 || asteroids[i - 1] == 0) count++;
        }

        if (count == 0) return asteroids;
        return asteroidCollision1(asteroids);
    }


}
